/*-------------------------------------------------------------------------
 *
 * ilist.h
 *		integrated/inline doubly- and singly-linked lists
 *
 * These list types are useful when there are only a predetermined set of
 * lists that an object could be in.  List links are embedded directly into
 * the objects, and thus no extra memory management overhead is required.
 * (Of course, if only a small proportion of existing objects are in a list,
 * the link fields in the remainder would be wasted space.  But usually,
 * it saves space to not have separately-allocated list nodes.)
 *
 * None of the functions here allocate any memory; they just manipulate
 * externally managed memory.  The APIs for singly and doubly linked lists
 * are identical as far as capabilities of both allow.
 *
 * Each list has a list header, which exists even when the list is empty.
 * An empty singly-linked list has a NULL pointer in its header.
 * There are two kinds of empty doubly linked lists: those that have been
 * initialized to NULL, and those that have been initialized to circularity.
 * (If a dlist is modified and then all its elements are deleted, it will be
 * in the circular state.)	We prefer circular dlists because there are some
 * operations that can be done without branches (and thus faster) on lists
 * that use circular representation.  However, it is often convenient to
 * initialize list headers to zeroes rather than setting them up with an
 * explicit initialization function, so we also allow the other case.
 *
 * EXAMPLES
 *
 * Here's a simple example demonstrating how this can be used.  Let's assume
 * we want to store information about the tables contained in a database.
 *
 * #include "lib/ilist.h"
 *
 * // 定义用于数据库的结构，包括一个列表头，以便稍后访问表列表中的节点。
 * // 定义表的结构。 注意存储prev/next列表链接的list_node元素。 list_node元素不必是第一个。
 * typedef struct my_database
 * {
 *		char	   *datname;
 *		dlist_head	tables;
 *		// ...
 * } my_database;
 *
 * // 创建一个数据库
 * // 并向其表列表中添加几个表
 * typedef struct my_table
 * {
 *		char	   *tablename;
 *		dlist_node	list_node;
 *		perm_t		permissions;
 *		// ...
 * } my_table;
 *
 * // 不要触碰这个
 * my_database *db = create_database();
 *
 * // 从链表中解开当前表
 * dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
 * ...
 * dlist_push_head(&db->tables, &create_table(db, "b")->list_node);
 *
 *
 * To iterate over the table list, we allocate an iterator variable and use
 * a specialized looping construct.  Inside a dlist_foreach, the iterator's
 * 'cur' field can be used to access the current element.  iter.cur points to
 * a 'dlist_node', but most of the time what we want is the actual table
 * information; dlist_container() gives us that, like so:
 *
 * dlist_iter	iter;
 * dlist_foreach(iter, &db->tables)
 * {
 *		my_table   *tbl = dlist_container(my_table, list_node, iter.cur);
 *		printf("we have a table: %s in database %s\n",
 *			   tbl->tablename, db->datname);
 * }
 *
 *
 * While a simple iteration is useful, we sometimes also want to manipulate
 * the list while iterating.  There is a different iterator element and looping
 * construct for that.  Suppose we want to delete tables that meet a certain
 * criterion:
 *
 * dlist_mutable_iter miter;
 * dlist_foreach_modify(miter, &db->tables)
 * {
 *		my_table   *tbl = dlist_container(my_table, list_node, miter.cur);
 *
 *		if (!tbl->to_be_deleted)
 *			continue;		// 由于这些列表从不管理内存，我们仍然可以在其被解开后访问表
 *
 *		// 从链表中解除当前表的链接
 *		dlist_delete(miter.cur);
 *		// 由于这些列表从不管理内存，我们可以在解除链接后仍然访问该表
 *		//
 *		drop_table(db, tbl);
 * }
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *		src/include/lib/ilist.h
 *-------------------------------------------------------------------------
 */
#ifndef ILIST_H
#define ILIST_H

/*
 * 启用额外调试。这是相当昂贵的，因此即使在 USE_ASSERT_CHECKING
 * 下也默认未启用。
 */
/* #define ILIST_DEBUG */

/*
 * 双向链表的节点。
 *
 * 将此嵌入需要成为双向链表一部分的结构中。
 */
typedef struct dlist_node dlist_node;
struct dlist_node
{
	dlist_node *prev;
	dlist_node *next;
};

/*
 * 双向链表的头。
 *
 * 非空列表在内部是循环链接的。循环链表的优点是在最常见的列表操作
 * 中不需要任何分支。空列表也可以表示为一对 NULL 指针，使初始化更为容易。
 */
typedef struct dlist_head
{
	/*
	 * head.next 要么指向列表的第一个元素；要么指向 &head 如果它是一个
	 * 循环空列表；或者指向 NULL 如果为空且不是循环的。
	 *
	 * head.prev 要么指向列表的最后一个元素；要么指向 &head 如果它是一个
	 * 循环空列表；或者指向 NULL 如果为空且不是循环的。
	 */
	dlist_node	head;
} dlist_head;


/*
 * 双向链表迭代器。
 *
 * 用作 dlist_foreach() 和 dlist_reverse_foreach() 中的状态。要获取
 * 当前迭代元素，请使用 'cur' 成员。
 *
 * 使用此方法的迭代 *不* 允许在迭代时修改列表！
 *
 * 注意：我们在这里使用一个额外的 "end" 字段，以避免在 dlist_foreach()
 * 宏中多次计算参数。
 */
typedef struct dlist_iter
{
	dlist_node *cur;			/* 当前元素 */
	dlist_node *end;			/* 我们将迭代到的最后一个节点 */
} dlist_iter;

/*
 * 双向链表迭代器，可在迭代时进行某些修改。
 *
 * 用作 dlist_foreach_modify() 中的状态。要获取当前元素，请使用 'cur' 成员。
 *
 * 使用此迭代器的迭代仅允许在当前迭代点修改链表。删除当前节点是可以的，但*不允许*插入或删除相邻节点。
 *
 * 注意：我们需要一个单独的类型用于可变迭代，以便在当前节点被删除或修改时存储 'next' 节点。
 */
typedef struct dlist_mutable_iter
{
	dlist_node *cur;			/* 当前元素 */
	dlist_node *next;			/* 我们将迭代到的下一个节点 */
	dlist_node *end;			/* 我们将迭代到的最后一个节点 */
} dlist_mutable_iter;

/*
 * 单向链表的节点。
 *
 * 将其嵌入需要成为单向链表一部分的结构中。
 */
typedef struct slist_node slist_node;
struct slist_node
{
	slist_node *next;
};

/*
 * 单向链表的头节点。
 *
 * 单向链表不是循环链接的，与双向链表相反；如果为空，我们只需将 head.next 设置为 NULL。这不会在通常的操作中产生任何额外的分支。
 */
typedef struct slist_head
{
	slist_node	head;
} slist_head;

/*
 * 单向链表迭代器。
 *
 * 用作 slist_foreach() 中的状态。要获取当前元素，请使用 'cur' 成员。
 *
 * 在迭代时允许修改链表，除了删除迭代器的当前节点；如果要继续后续迭代，删除该节点需要小心。（这样做并且删除或插入相邻列表元素可能会导致问题；此外，如果用户释放当前节点的存储，继续迭代是不安全的。）
 *
 * 注意：这并不真的需要一个额外的结构，我们可以直接使用 slist_node *。我们倾向于为一致性使用一个单独的类型。
 */
typedef struct slist_iter
{
	slist_node *cur;
} slist_iter;

/*
 * 允许在迭代时进行某些修改的单向链表迭代器。
 *
 * 用作 slist_foreach_modify() 中的状态。要获取当前元素，请使用 'cur' 成员。
 *
 * 在迭代时允许的唯一链表修改是通过 slist_delete_current() 删除当前节点（*不是* slist_delete()）。在当前节点相邻处插入或删除节点会导致问题。
 */
typedef struct slist_mutable_iter
{
	slist_node *cur;			/* 当前元素 */
	slist_node *next;			/* 我们将迭代到的下一个节点 */
	slist_node *prev;			/* 删除时的前一个节点 */
} slist_mutable_iter;


/* 静态初始化器 */
#define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}}
#define SLIST_STATIC_INIT(name) {{NULL}}


/* 对于太大而无法内联的函数的原型 */

/* 注意：这是 O(n)；考虑使用 slist_delete_current() */
extern void slist_delete(slist_head *head, slist_node *node);

#ifdef ILIST_DEBUG
extern void dlist_check(dlist_head *head);
extern void slist_check(slist_head *head);
#else
/*
 * 这些看似无用的 void 强制转换存在于这里，以使编译器在许多函数中对于参数未使用保持安静，在非调试编译中，传递链表头指针的唯一目的是能够运行这些检查。
 */
#define dlist_check(head)	((void) (head))
#define slist_check(head)	((void) (head))
#endif							/* ILIST_DEBUG */

/* 双向链表实现 */

/*
 * 初始化一个双向链表。
 * 之前的状态将被废弃而不进行任何清理。
 */
static inline void
dlist_init(dlist_head *head)
{
	head->head.next = head->head.prev = &head->head;
}

/*
 * 列表是否为空？
 *
 * 空列表的第一个 'next' 指针要么设置为 NULL，要么指向自身。
 */
static inline bool
dlist_is_empty(dlist_head *head)
{
	dlist_check(head);

	return head->head.next == NULL || head->head.next == &(head->head);
}

/*
 * 在列表的开头插入一个节点。
 */
static inline void
dlist_push_head(dlist_head *head, dlist_node *node)
{
	if (head->head.next == NULL)	/* 将 NULL 头转换为循环 */
		dlist_init(head);

	node->next = head->head.next;
	node->prev = &head->head;
	node->next->prev = node;
	head->head.next = node;

	dlist_check(head);
}

/*
 * 在列表的末尾插入一个节点。
 */
static inline void
dlist_push_tail(dlist_head *head, dlist_node *node)
{
	if (head->head.next == NULL)	/* 将 NULL 头转换为循环 */
		dlist_init(head);

	node->next = &head->head;
	node->prev = head->head.prev;
	node->prev->next = node;
	head->head.prev = node;

	dlist_check(head);
}

/*
 * 在*同一列表*中在另一个节点后插入节点。
 */
static inline void
dlist_insert_after(dlist_node *after, dlist_node *node)
{
	node->prev = after;
	node->next = after->next;
	after->next = node;
	node->next->prev = node;
}

/*
 * 在*同一列表*中在另一个节点前插入节点。
 */
static inline void
dlist_insert_before(dlist_node *before, dlist_node *node)
{
	node->prev = before->prev;
	node->next = before;
	before->prev = node;
	node->prev->next = node;
}

/*
 * 从其列表中删除 'node'（它必须在一个列表中）。
 */
static inline void
dlist_delete(dlist_node *node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
}

/*
 * 从列表中移除并返回第一个节点（必须有一个）。
 */
static inline dlist_node *
dlist_pop_head_node(dlist_head *head)
{
	dlist_node *node;

	Assert(!dlist_is_empty(head));
	node = head->head.next;
	dlist_delete(node);
	return node;
}

/*
 * 将元素从其在列表中的当前位置移动到同一列表的头位置。
 *
 * 如果 'node' 尚未成为列表的一部分，则行为未定义。
 */
static inline void
dlist_move_head(dlist_head *head, dlist_node *node)
{
	/* 如果它已经在头部，则快速路径 */
	if (head->head.next == node)
		return;

	dlist_delete(node);
	dlist_push_head(head, node);

	dlist_check(head);
}

/*
 * 将元素从其在列表中的当前位置移动到同一列表的尾部位置。
 *
 * 如果 'node' 尚未成为列表的一部分，则行为未定义。
 */
static inline void
dlist_move_tail(dlist_head *head, dlist_node *node)
{
	/* 如果它已经在尾部，则快速路径 */
	if (head->head.prev == node)
		return;

	dlist_delete(node);
	dlist_push_tail(head, node);

	dlist_check(head);
}

/*
 * 检查 'node' 是否有后续节点。
 * 注意：如果 'node' 不在列表中，则不可靠。
 */
static inline bool
dlist_has_next(dlist_head *head, dlist_node *node)
{
	return node->next != &head->head;
}

/*
 * 检查 'node' 是否有前一节点。
 * 注意：如果 'node' 不在列表中，则不可靠。
 */
static inline bool
dlist_has_prev(dlist_head *head, dlist_node *node)
{
	return node->prev != &head->head;
}

/*
 * 返回列表中的下一个节点（必须有一个）。
 */
static inline dlist_node *
dlist_next_node(dlist_head *head, dlist_node *node)
{
	Assert(dlist_has_next(head, node));
	return node->next;
}

/*
 * 返回列表中的前一个节点（必须有一个）。
 */
static inline dlist_node *
dlist_prev_node(dlist_head *head, dlist_node *node)
{
	Assert(dlist_has_prev(head, node));
	return node->prev;
}

/* 内部支持函数以获取头元素的结构地址 */
static inline void *
dlist_head_element_off(dlist_head *head, size_t off)
{
	Assert(!dlist_is_empty(head));
	return (char *) head->head.next - off;
}

/*
 * 返回列表中的第一个节点（必须有一个）。
 */
static inline dlist_node *
dlist_head_node(dlist_head *head)
{
	return (dlist_node *) dlist_head_element_off(head, 0);
}

/* 内部支持函数以获取尾元素的结构地址 */
static inline void *
dlist_tail_element_off(dlist_head *head, size_t off)
{
	Assert(!dlist_is_empty(head));
	return (char *) head->head.prev - off;
}

/*
 * 返回列表中的最后一个节点（必须有一个）。
 */
static inline dlist_node *
dlist_tail_node(dlist_head *head)
{
	return (dlist_node *) dlist_tail_element_off(head, 0);
}

/*
 * 返回'type'类型包含的结构，其中'membername'是由'ptr'指向的dlist_node。
 *
 * 这用于将dlist_node *转换回其包含的结构。
 */
#define dlist_container(type, membername, ptr)								\
	(AssertVariableIsOfTypeMacro(ptr, dlist_node *),						\
	 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),	\
	 ((type *) ((char *) (ptr) - offsetof(type, membername))))

/*
 * 返回列表中第一个元素的地址。
 *
 * 列表不能为空。
 */
#define dlist_head_element(type, membername, lhead)							\
	(AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),	\
	 (type *) dlist_head_element_off(lhead, offsetof(type, membername)))

/*
 * 返回列表中最后一个元素的地址。
 *
 * 列表不能为空。
 */
#define dlist_tail_element(type, membername, lhead)							\
	(AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node),	\
	 ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))

/*
 * 遍历由'lhead'指向的列表，将状态存储在'iter'中。
 *
 * 使用iter.cur访问当前元素。
 *
 * 在迭代期间*不允许*操作列表。
 */
#define dlist_foreach(iter, lhead)											\
	for (AssertVariableIsOfTypeMacro(iter, dlist_iter),						\
		 AssertVariableIsOfTypeMacro(lhead, dlist_head *),					\
		 (iter).end = &(lhead)->head,										\
		 (iter).cur = (iter).end->next ? (iter).end->next : (iter).end;		\
		 (iter).cur != (iter).end;											\
		 (iter).cur = (iter).cur->next)

/*
 * 遍历由'lhead'指向的列表，将状态存储在'iter'中。
 *
 * 使用iter.cur访问当前元素。
 *
 * 使用此方法的迭代仅允许在当前迭代点更改列表。 删除当前节点是可以的，但*不*可以插入或删除相邻节点。
 */
#define dlist_foreach_modify(iter, lhead)									\
	for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter),				\
		 AssertVariableIsOfTypeMacro(lhead, dlist_head *),					\
		 (iter).end = &(lhead)->head,										\
		 (iter).cur = (iter).end->next ? (iter).end->next : (iter).end,		\
		 (iter).next = (iter).cur->next;									\
		 (iter).cur != (iter).end;											\
		 (iter).cur = (iter).next, (iter).next = (iter).cur->next)

/*
 * 以相反的顺序遍历列表。
 *
 * 在迭代期间*不允许*操作列表。
 */
#define dlist_reverse_foreach(iter, lhead)									\
	for (AssertVariableIsOfTypeMacro(iter, dlist_iter),						\
		 AssertVariableIsOfTypeMacro(lhead, dlist_head *),					\
		 (iter).end = &(lhead)->head,										\
		 (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end;		\
		 (iter).cur != (iter).end;											\
		 (iter).cur = (iter).cur->prev)


/* 单链表实现 */

/*
 * 初始化一个单链表。
 * 先前的状态将被丢弃而不进行任何清理。
 */
static inline void
slist_init(slist_head *head)
{
	head->head.next = NULL;
}

/*
 * 列表为空吗？
 */
static inline bool
slist_is_empty(slist_head *head)
{
	slist_check(head);

	return head->head.next == NULL;
}

/*
 * 在列表的开头插入一个节点。
 */
static inline void
slist_push_head(slist_head *head, slist_node *node)
{
	node->next = head->head.next;
	head->head.next = node;

	slist_check(head);
}

/*
 * 在*同一列表*中在另一个节点后插入节点。
 */
static inline void
slist_insert_after(slist_node *after, slist_node *node)
{
	node->next = after->next;
	after->next = node;
}

/*
 * 从列表中移除并返回第一个节点（必须有一个）。
 */
static inline slist_node *
slist_pop_head_node(slist_head *head)
{
	slist_node *node;

	Assert(!slist_is_empty(head));
	node = head->head.next;
	head->head.next = node->next;
	slist_check(head);
	return node;
}

/*
 * 检查'nod'是否有后续节点。
 */
static inline bool
slist_has_next(slist_head *head, slist_node *node)
{
	slist_check(head);

	return node->next != NULL;
}

/*
 * 返回列表中的下一个节点（必须有一个）。
 */
static inline slist_node *
slist_next_node(slist_head *head, slist_node *node)
{
	Assert(slist_has_next(head, node));
	return node->next;
}

/* 内部支持函数以获取头元素的结构地址 */
static inline void *
slist_head_element_off(slist_head *head, size_t off)
{
	Assert(!slist_is_empty(head));
	return (char *) head->head.next - off;
}

/*
 * 返回列表中的第一个节点（必须有一个）。
 */
static inline slist_node *
slist_head_node(slist_head *head)
{
	return (slist_node *) slist_head_element_off(head, 0);
}

/*
 * 删除迭代器当前指向的列表元素。
 *
 * 小心：这会修改iter->cur，因此在当前循环迭代中不要再次使用它。
 */
static inline void
slist_delete_current(slist_mutable_iter *iter)
{
	/*
	 * 更新前一个元素的前向链接。 如果迭代处于
	 * 第一个列表元素，iter->prev将指向列表头的“head”字段，
	 * 因此我们不需要为此提供特殊情况。
	 */
	iter->prev->next = iter->next;

	/*
	 * 将cur重置为prev，以便在slist_foreach_modify()推进到下一个
	 * 有效列表元素后，prev将继续指向先前的有效列表元素。
	 */
	iter->cur = iter->prev;
}

/*
 * 返回'type'类型包含的结构，其中'membername'是由'ptr'指向的slist_node。
 *
 * 这用于将slist_node *转换回其包含的结构。
 */
#define slist_container(type, membername, ptr)								\
	(AssertVariableIsOfTypeMacro(ptr, slist_node *),						\
	 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),	\
	 ((type *) ((char *) (ptr) - offsetof(type, membername))))

/*
 * 返回列表中第一个元素的地址。
 *
 * 列表不能为空。
 */
#define slist_head_element(type, membername, lhead)							\
	(AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node),	\
	 (type *) slist_head_element_off(lhead, offsetof(type, membername)))

/*
 * 遍历由'lhead'指向的列表，将状态存储在'iter'中。
 *
 * 使用iter.cur访问当前元素。
 *
 * 在迭代时允许修改列表，唯一的例外是删除迭代器当前的节点；
 * 如果要继续迭代，则删除该节点时需要小心。 （这样做并同时删除或插入相邻列表元素可能会导致异常行为；另外，如果用户释放当前节点的存储，则继续迭代是不安全的。）
 */
#define slist_foreach(iter, lhead)											\
	for (AssertVariableIsOfTypeMacro(iter, slist_iter),						\
		 AssertVariableIsOfTypeMacro(lhead, slist_head *),					\
		 (iter).cur = (lhead)->head.next;									\
		 (iter).cur != NULL;												\
		 (iter).cur = (iter).cur->next)

/*
 * 遍历由'lhead'指向的列表，将状态存储在'iter'中。
 *
 * 使用iter.cur访问当前元素。
 *
 * 迭代时唯一允许的列表修改是通过slist_delete_current()删除当前节点（*不是*slist_delete()）。 在当前节点相邻的节点插入或删除将导致异常行为。
 */
#define slist_foreach_modify(iter, lhead)									\
	for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter),				\
		 AssertVariableIsOfTypeMacro(lhead, slist_head *),					\
		 (iter).prev = &(lhead)->head,										\
		 (iter).cur = (iter).prev->next,									\
		 (iter).next = (iter).cur ? (iter).cur->next : NULL;				\
		 (iter).cur != NULL;												\
		 (iter).prev = (iter).cur,											\
		 (iter).cur = (iter).next,											\
		 (iter).next = (iter).next ? (iter).next->next : NULL)

#endif							/* ILIST_H */
